package CommonAlgs.recursion;

/**
 * 汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，
 * 大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。
 * 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
 * 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
 * 游戏目标：将所有圆盘套在另一根柱子上。
 * f(n,A->C) = f(n-1,A->B)+(n)A->C+f(n-1,B->C)
 */
public class Tower_of_Hanoi {
    public static void main(String[] args) {
        int n = 10;
        char a = 'A', b = 'B', c = 'C';
        hanoi(n, a, b, c);
    }
    //参数1表示src 参数2表示辅助, 参数3表示dest
    private static void hanoi(int n, char a, char b, char c) {
        if (n==1) System.out.printf("%c->%c\n",a,c);
        else {
            hanoi(n-1,a,c,b);
            System.out.printf("%c->%c\n",a,c);
            hanoi(n-1,b,a,c);
        }
    }
}
